package leetcode.code572;

import leetcode.helper.tree.TreeNode;

public class Solution extends Solution572 {

	@Override
	public boolean isSubtree(TreeNode root, TreeNode subRoot) {
		return this.isSubtree(root, subRoot, false);
	}

	public boolean isSubtree(TreeNode root, TreeNode subRoot, boolean flag) {
		if (root == null && subRoot == null)
			return true;
		if ((root == null && subRoot != null) || (root != null && subRoot == null))
			return false;
		if (flag || root.val == subRoot.val) {
			boolean left = this.isSubtree(root.left, subRoot.left, true);
			boolean right = this.isSubtree(root.right, subRoot.right, true);
			if (left && right && root.val == subRoot.val)
				return true;
			else if (flag) {
				return false;
			}
		}
		boolean left = this.isSubtree(root.left, subRoot, false);
		if (left)
			return true;
		boolean right = this.isSubtree(root.right, subRoot, false);
		if (right)
			return true;
		return false;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
